package algorithm.leetcode.I101to200;

public class Q115 {

    public int numDistinct(String s, String t) {
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();

        // dp[i][j] 代表 T 前 i 字符串可以由 S j 字符串组成最多个数
        // 当 S[j] == T[i] , dp[i][j] = dp[i-1][j-1] + dp[i][j-1],例如s=rabb,t=rab时,dp[i-1][j-1]表示s=rab,t=ra的情况,dp[i][j-1]表示s=rab,t=rab的情况;
        // 当 S[j] != T[i] , dp[i][j] = dp[i][j-1],等式右边其实也就是也是上面一行的后面一项,主要这个有点难想通.长字符串第j位和短字符串第i位不同,那么dp[i][j]应该就等于长字符串砍掉最后一位再和短字符串匹配的结果
        // dp数组优化,为s和t前面添加一个空字符串""
        int[][] dp = new int[tChars.length+1][sChars.length+1];

        for (int i = 0; i <= tChars.length; i++) {
            for (int j = 0; j <= sChars.length; j++) {
                if (i == 0) dp[i][j] = 1; // 长字符串随便哪一位都可以由短字符串第一个空字符串""匹配上,故结果为1
                else if (j == 0) dp[i][j] = 0; // 一旦短字符串开始变长,就永远无法组成长字符串第一个空字符串"",故为0
                else {
                    if (sChars[j-1] == tChars[i-1]) dp[i][j] = dp[i-1][j-1]+dp[i][j-1];
                    else dp[i][j] = dp[i][j-1];
                }
            }
        }
        return dp[tChars.length][sChars.length];
    }

    public static void main(String[] args) {
        Q115 q115 = new Q115();
        System.out.println(q115.numDistinct("babgbag", "bag"));
    }

}
